// 二叉树的前序遍历
// 递归

class TreeNode {
    constructor(data) {
        this.data = data;
        this.left = null;
        this.right = null;
    }
}

// 创建二叉树
function createBinaryTree(arr) {
    if (arr.length === 0) return null;
    let node = null;
    let data = arr.shift();
    if (data !== null) {
        node = new TreeNode(data);
        node.left = createBinaryTree(arr);
        node.right = createBinaryTree(arr);
    }
    return node;
}

// 前序 递归
function preOrder(node) {
    if (node === null) return;
    console.log(node.data);
    preOrder(node.left);
    preOrder(node.right);
}

// 中序 递归
function inOrder(node) {
    if (node === null) return;
    inOrder(node.left);
    console.log(node.data);
    inOrder(node.right);
}

// 后序 递归
function postOrder(node) {
    if (node === null) return;
    postOrder(node.left);
    postOrder(node.right);
    console.log(node.data);
}

// 前序 栈
function preOrderStack(node) {
    const stack = new Array();
    while (node !== null || stack.length > 0) {
        while (node !== null) {
            stack.push(node);
            console.log(node.data);
            node = node.left;
        }
        node = stack.pop();
        node = node.right;
    }
}

// 中序 栈
function inOrderStack(node) {
    const stack = new Array();
    while (node !== null || stack.length > 0) {
        while (node !== null) {
            stack.push(node);
            node = node.left;
        }
        node = stack.pop();
        console.log(node.data);
        node = node.right;
    }
}

// 后序 栈

// 层序 队列
function levelOrderQueue(node) {
    const queue = new Array();
    queue.push(node);
    while (queue.length > 0) {
        node = queue.shift();
        console.log(node.data);
        if (node.left !== null) {
            queue.push(node.left);
        }
        if (node.right !== null) {
            queue.push(node.right);
        }
    }
}

const arr = [1,2,4,null,null,5,null,null,3,null,6,null,null];
const treeNode = createBinaryTree(arr);
// console.log(treeNode);
// preOrder(treeNode);
// inOrder(treeNode);
// postOrder(treeNode);

// preOrderStack(treeNode);
// inOrderStack(treeNode);

levelOrderQueue(treeNode);


/* 二叉树遍历的应用 */

// 1. 遍历出所有叶子节点
// 利用前序遍历，如果都没有左右，则打印
function preOrderLeaf(node) {
    if (node === null) return;
    if (node.left === null && node.right === null) {
        console.log(node.data);
    }
    preOrderLeaf(node.left);
    preOrderLeaf(node.right);
}
// preOrderLeaf(treeNode);

// 2. 求二叉树高度
function getBinarytreeHeight(node) {
    let lH, rH, maxH;
    if (node !== null) {
        lH = getBinarytreeHeight(node.left);
        rH = getBinarytreeHeight(node.right);
        maxH = lH > rH ? lH : rH;
        return maxH + 1;
    } else {
        return 0;
    }
}
// const btHeight = getBinarytreeHeight(treeNode);
// console.log(btHeight);

// 3. 